package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

//归并排序（分治算法）：从小到大排序(关键：先将数组中的每个元素通过递归拆分成独立元素，又通过回溯进行排序合并)
public class MergeSort {

	public static void main(String[] args) {
		/*该数组运行顺序，先进行左递归拆分数组，拆分完后回溯到栈顶对1和6进行合并，之后回溯进行3右递归拆分，
		不满足递归条件(left <right)回溯，然后对1,6和3合并，之后回溯进行4和9右递归拆分，拆分完后
		进行合并，之后对1,3,6和4,9进行合并，之后回溯进行5,2,8,0,7右递归拆分，以此类推...
		（先进行左递归，左递归到最后，通过回溯进行右递归，右递归顺序与左递归相反，左递归是从开始到最后，
		右递归是回溯的时候进行的，是最后到开始,例：4和9的拆分是1,6和3合并完之后（变成有序）通过回溯到到
		1,3,6,4,9进行对4,9拆分，然后合并）*/
		int[] nums= {1,6,3,4,9,5,2,8,0,7};
		/*int[] nums = new int[80000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = (int) (Math.random() * 80000);
		}*/
		Date d1 = new Date();
		SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");// 日期格式
		System.out.println("排序前的时间：" + s.format(d1));
//		mergeSort(nums, 0, nums.length - 1);
		int[] res = mergeSort(nums);
		Date d2 = new Date();
		System.out.println("排序后的时间：" + s.format(d2));
		 System.out.println(Arrays.toString(res));

	}

	// 拆分+合并
	public static void mergeSort(int[] nums, int left, int right) {
		int[] temp = new int[nums.length];
		int mid = (left + right) / 2;
		if (left < right) {
			/*左递归拆分数组，左递归拆分完后回溯到栈顶的数组进行右递归拆分，
			每拆分一个右递归就对该次划分的数组元素进行排序合并merge()*/
			mergeSort(nums, left, mid);
			/*右递归拆分数组*/
			mergeSort(nums, mid + 1, right);
			/*合并*/
			merge(nums, left, mid, right, temp);
		}
	}

	// 合并
	public static void merge(int[] nums, int left, int mid, int right, int[] temp) {
		int i = left;
		int j = mid + 1;
		int t = 0;
		// 将左右两边有序的数组按大小填充到temp数组，直到两边的有序序列有一边处理完
		while (i <= mid && j <= right) {
			if (nums[i] < nums[j]) {
				temp[t] = nums[i];
				i++;
				t++;
			} else {
				temp[t] = nums[j];
				j++;
				t++;
			}
		}
		// 把左边剩余的数填充到temp数组
		while (i <= mid) {
			temp[t] = nums[i];
			i++;
			t++;
		}
		// 把右边剩余的数填充到temp数组
		while (j <= right) {
			temp[t] = nums[j];
			j++;
			t++;
		}
		// 将temp数组拷贝回原数组nums
		t = 0;
		int templeft = left;
		while (templeft <= right) {
			nums[templeft] = temp[t];
			templeft++;
			t++;
		}
	}



	//当合并两个无序数组时，先将两个数组拆分成独立元素（独立元素肯定是有序的），然后再合并
	public static int[] mergeSort(int[] arr){
		if (arr.length<2){
			return arr;
		}
		int mid=arr.length/2;
		int[] leftArr= Arrays.copyOfRange(arr,0,mid);
		int[] rightArr= Arrays.copyOfRange(arr,mid,arr.length);
		int[] arr1 = mergeSort(leftArr);
		int[] arr2 = mergeSort(rightArr);
		return merge(arr1, arr2);
	}

	//合并两个有序数组，
	public static int[] merge(int[] arr1, int[] arr2){
		int[] newArr = new int[arr1.length + arr2.length];
		for (int i = 0,i1=0,i2=0; i < newArr.length; i++) {
			if (i1>=arr1.length){//arr1临界
				newArr[i]=arr2[i2++];//将i2索引下的值赋给newArr后+1
			}else if (i2>=arr2.length){//arr2临界
				newArr[i]=arr1[i1++];
			}else if (arr1[i1]<=arr2[i2]){
				newArr[i]=arr1[i1++];
			}else {
				newArr[i]=arr2[i2++];
			}
		}
		return newArr;
	}
}
